#define _CRT_SECURE_NO_WARNINGS
//
//#include <stdio.h>
//
//int Fun(int n)
//{
//	if (n == 5)
//		return 2;
//	else
//		return 2 * Fun(n + 1);
//}
//
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int ret = Fun(n);
//	printf("%d\n", ret);
//	return 0;
//}
//
//#include <stdio.h>
//
//int Fac(int n)
//{
//	if (n == 1)
//		return 1;
//	else
//		return n*Fac(n - 1);
//}
//
//int main()
//{
//	int n = 0;
//	while(1)
//	{
//	scanf("%d", &n);
//	int ret = Fac(n);
//	printf("%d\n", ret); 
//	}
//	return 0;
//}

#include <stdio.h>

//int DigitSum (int n)
//{
//	int m = 0;
//	int sum = 0;
//	for (m = 0; m < 4; m++)
//	{
//		sum = sum + n % 10;
//		n = n / 10;
//	}
//	return sum;
//} 

//int DigitSum(int n)
//{
//	if (n < 9)
//		return n;
//	else
//		return n % 10 + (DigitSum(n / 10));
//
//
//}
//
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int ret = DigitSum(n);
//	printf("%d\n", ret);
//	return 0;
//}

//#include <stdio.h>

//int my_strlen(char* str)
//{
//	if (*str == '\0')
//		return 0;
//	else
//		return 1 + my_strlen(str+1);
//}

//
//#include <stdio.h>
//int my_strlen(char* str)
//{
//	int count = 0;
//	while (*str != '\0')
//	{
//		count++;
//		str++;
//		
//	}
//	return count;
//}
//
//int main()
//{
//	char arr[] = "asdfghjkl";
//	int len = my_strlen(arr);
//	printf("%d\n", len);
//	return 0;
//}

//
//
//#include<stdio.h>
//void  Fn(int i)
//{
//	if (i > 9)
//	{
//		Fn(i / 10);
//	}
//	printf("%d ", i%10);
//}
//
//int main()
//{
//	int i = 0;
//	scanf("%d", &i);
//    Fn(i);
//	return 0;
//}

// 1 1 2 3  5
//#include <stdio.h>

//int Fib(int i)
//{
//	if (i < 3)
//		return 1;
//	else
//		return  Fib(i - 2) + Fib(i - 1);
//	
//}


//int Fib(int i)
//{
//	int a = 1;
//	int b = 1;
//	int c = 1;
//	while (i > 2)
//	{
//		 c = a + b;
//		 a = b;
//		 b = c;
//		 i--;
//	}
//	return c;
//}
//
//int main()
//{
//	int i = 1;
//	while (i)
//	{
//	scanf("%d", &i);
//	int ret = Fib(i);
//	printf("%d\n", ret);
//	}
//	return 0;
//}
//
//
//#include <stdio.h>
//
//
//char  Re(char* arr[])
//{
//	if (*arr != '\0')
//		return Re(arr++);
//}
//
//int main()
//{
//	char arr[] = "abcdef";
//
//    char ret = Re(arr);
//	printf("%s ", ret);
//	return 0;
//}



//#include <stdio.h>
//
//int Fac(int n)
//{
//	if (n == 1)
//		return 1;
//	else
//		return n * Fac(n - 1);
//
//}
//
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int ret = Fac(n);
//	printf("%d", ret);
//	return 0;
//}
//
//
//#include <stdio.h>
//
//int Fac(int n)
//{
//	int i = 0;
//	int c = 1;
//	for (i = 1; i <= n; i++)
//	{
//		c *= i;
//	}
//	return  c;
//}
//
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int ret = Fac(n);
//	printf("%d", ret);
//
//	return 0;
//}